#include <iostream>
using namespace std;

int partial(int* sz, int p, int r) {
	int i = p - 1, j = p;
	int key = sz[r];

	for (j=p; j<r; j++) {
		if (sz[j] <= key) {
			i++;

			int tmp = sz[i];
			sz[i] = sz[j];
			sz[j] = tmp;
		}
	}
	
	int e = sz[r];
	sz[r] = sz[i+1];
	sz[i+1] = e;

	return i+1;
}

int get_nth(int sz[], int s, int n) {
	int k = -1;
	int b = 0, e = s-1;

	while (k != n) {
		if (k > n)
			e = k - 1;
		else
			b = k + 1;

		k = partial(sz, b, e);
	}

	return sz[k];
}

void quick_sort(int* sz, int p, int r) {
	if (p < r)
	{
		int q = partial(sz, p, r);
		quick_sort(sz, p, q-1);
		quick_sort(sz, q+1, r);
	}
}

//int main()
//{
//	int sz[] = {2,8,7,1,3,5,6,4};
//	quick_sort(sz, 0, 7);
//
//	int sz1[] = {2,8,7,1,3,5,6,4};
//	int res = get_nth(sz1, 8, 4);
//
//	return 0;
//}

//int main() {
//	int c, n, m, s, t, k;
//	int d[100000];
//	cin>>c;
//
//	while (c--) {
//		cin>>n>>m;
//		for (int i=0; i<n; i++)
//			cin>>d[i];
//
//		for (int j=0; j<m; j++)	{
//			cin>>s>>t>>k;
//			cout<<get_nth(d+s-1, t-s+1, k-1)<<endl;;
//		}
//	}
//
//	return 0;
//}